package leetcode;

import java.util.Stack;

public class bawu {
    public static int maximalRectangle(char[][] nums) {
        if(nums.length==1&&nums[0].length==1){
            return nums[0][0]-'0';
        }
        int rows=nums.length;
        int cols=nums[0].length;
        int[] heights=new int[cols];
        int sum=0;
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                if(nums[i][j]-'0'==1){
                    heights[j]=heights[j]+1;
                }
                if(nums[i][j]-'0'==0){
                    heights[j]=0;
                }

            }
            sum=Math.max(maxjuxing(heights),sum);
        }
        return sum;
    }
    public static int maxjuxing(int[] heights){
        Stack<Integer> stack=new Stack<>();
        stack.push(-1);
        int max=0;
        for(int i=0;i<heights.length;i++){
            while(stack.peek()!=-1&&heights[i]<heights[stack.peek()]){
                int m=stack.pop();
                int h=heights[m];
                int width=i-stack.peek()-1;
                max=Math.max(max,h*width);
            }
            stack.push(i);
        }
        while(stack.peek()!=-1){
            int h=heights[stack.pop()];
            int width=heights.length-stack.peek()-1;
            max=Math.max(max,h*width);
        }
        return max;

    }

    public static void main(String[] args) {
        char[][] array={
                {'1', '0', '1', '0', '0'},
                {'1', '0', '1', '1', '1'},
                {'1', '1', '1', '1', '1'},
                {'1', '0', '0', '1', '0'}
        };
        int i = maximalRectangle(array);
        System.out.println(i);


    }
}
